/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-17 11:25:06
 * @LastEditors: lily
 * @LastEditTime: 2021-05-17 17:23:09
 */
/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
//  思想：回溯法
//  https://leetcode-cn.com/problems/word-search/solution/79dan-ci-sou-suo-dfs-js-by-suukii/
//  O(mn3^L) mn为board长与宽，l为word长度 O(mn)

var exist = function (board, word) {
    const rowLen = board.length, colLen = board[0].length
    const offest = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    var outsideBoard = function (x, y) {
        return x < 0 || x >= rowLen || y < 0 || y >= colLen;
    }

    // x y表示坐标，i表示word第i位
    var dfs = (x, y, i) => {
        if (i === word.length) return true
        // 越界表示没有
        if (i > word.length || outsideBoard(x, y)) return false
        // 剪枝
        if (board[x][y] !== word[i]) return false
        let char = board[x][y]
        // 标记用过
        board[x][y] = '*'
        let res = offest.some(([ox, oy]) => dfs(x + ox, y + oy, i + 1))
        // 回溯标记为原来的样子
        board[x][y] = char
        return res
    }
    // 对每一个进行判断
    return board.some((row, x) => row.some((cell, y) => dfs(x, y, 0)))
};
// @lc code=end

console.log(exist([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE"));